/*下面的程序在一个整形平衡二叉树中插入一个元素，求解的过程：
**采用递归的思想，如果插入元素值小于头结点，则插入头结点的左子树；
**否则插入右子树，向下递归，直到找到空位置为止
*/
#include<iostream>
#include<stdio.h>

typedef struct btnodetype   //定义节点
{
    btnodetype(int val) //初始化函数
    {
        _val=val;
        _cnt=1;
        _lchild=0;
        _rchild=0;
    }
    int _val;   //结点的值
    int _cnt;   //出现的次数，即纪录重复值
    struct btnodetype *_lchild; //左子树
    struct btnodetype *_rchild; //右子树
}btnode;

void add(const int &value,btnode *(&root));

void addtonode(btnode *(&node),const int &value)
{
    if(value==node->_val)   //如果插入节点和本节点值相同，则增加出现的次数即可
    {
        (node->_cnt)++;
    }
    else if(value>node->_val)   //判断插入节点应插入右边
    {
        if(node->_rchild==0)    //右子树为空，创建新节点
        {
            //btnode *temp=new btnode(value);
            btnode *temp=0;
            add(value,temp);
            node->_rchild=temp;
        }
        else    //右子树非空
        {
            addtonode(node->_rchild,value);
        }
    }
    else    //插入左边
    {
        /*类似节点插入左边的情况*/
        if(node->_lchild==0)    //左子树为空，创建新节点
        {
            //btnode *temp=new btnode(value);
            btnode *temp=0;
            add(value,temp);
            node->_lchild=temp;
        }
        else    //左子树非空
        {
            addtonode(node->_lchild,value);
        }
    }
}

void add(const int &value,btnode *(&root))
{
    if(root==0) //如果树为空
    {
        /**/
        root=new btnode(value);
    }
    else    //如果是非空树，则调用插入函数插入该节点
    {
        addtonode(root,value);
    }
}

//中序遍历函数，要求输出每个节点后换行
bool mid_traversal_node(btnode *root)
{
    if(root==0)
    {
        return false;
    }
    mid_traversal_node(root->_lchild);
    printf("val:%d\n",root->_val);
    mid_traversal_node(root->_rchild);;
    return true;
}

int main()
{
    btnode *root=0;
    //printf("%d\n",root->_val);
    add(10,root);
    add(1,root);
    add(20,root);
    add(30,root);
    add(9,root);
    add(8,root);
    add(13,root);
    mid_traversal_node(root);
}
